package problem174_Dungeon_Game;
/**
 * dp[i][j]表示位置i，j需要的最小血量，
 * dp[i][j]=Math.min（down,right）；
 * down=Math.max(1,dp[i][j+1]-dungeon[i][j]);
 * right=Math.max(1,dp[i+1][j]-dungeon[i][j]);
 * 
 * @author I321035
 *
 */
public class Solution {
	public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length,n=dungeon[0].length;
		int[][] dp=new int[m][n];
		dp[m-1][n-1]=Math.max(1, 1-dungeon[m-1][n-1]);
		//最后一行
		for(int i=n-2;i>=0;i--){
			dp[m-1][i]=Math.max(1, dp[m-1][i+1]-dungeon[m-1][i]);
		}
		//最后=一列
		for(int i=m-2;i>=0;i--){
			dp[i][n-1]=Math.max(1, dp[i+1][n-1]-dungeon[i][n-1]);
		}
		for(int i=m-2;i>=0;i--){
			for(int j=n-2;j>=0;j--){
				int down=Math.max(1, dp[i+1][j]-dungeon[i][j]);
				int right=Math.max(1, dp[i][j+1]-dungeon[i][j]);
				dp[i][j]=Math.min(down, right);
			}
		}
		return dp[0][0];
	}
}
